<template>
    <div class="demo-collapse">
        <el-collapse v-model="activeNames" @change="handleChange">
            <el-collapse-item title="解题思路" name="thinking">
                <div>
                    <div>
                        本质上就是从i个物品中选择一定数量的物品在一定空间限制的前提下，求这些物品的最大总价值，
                        我们可以定义一个二维数组dp[i][j]，这个数组的值就表示从前i件物品进行选择，
                        在不超过容量j的前提下所满足最大的物品总价值。（注：此处的第i件物品对应与数组下标i）
                    </div>
                    <div>
                        当只有一个物品时，如果该物品的体积v不大于背包容量j，则初始值dp[0][j]=w[0]，否则dp[0][j]=0。
                    </div>
                    <div>
                        对于第i件物品，设它的所占容量为v[i]，价值为w[i]，我们可以选择该物品也可以不选择该物品，
                        如果不选择该物品则dp[i][j]=dp[i-1][j]dp[i][j]=dp[i−1][j]，
                        如果选择该物品有两种情况：
                    </div>
                    <div>
                        背包剩余空间不够了，那么此时就无法选择该物品，
                        dp[i][j] = dp[i−1][j] 
                    </div>
                    <div>
                        背包剩余空间充足，那么此时的物品总价值为
                        dp[i][j] = dp[i−1][j−v[i]] + w[i] 
                    </div>
                    <div>
                        综上，转移方程为
                        dp[i][j] = max(dp[i−1][j],dp[i−1][j−v[i]]+w[i])
                    </div>
                </div>
            </el-collapse-item>
            <el-collapse-item title="代码实现" name="code">
                <!-- <el-image style="width:100%" :src="url" :fit="fit" loading="lazy"></el-image> -->
                <div v-highlight>
                    <div>C/C++:</div>
                    <pre class="language-javascript">
                      <code>
                        #include&lt;stdio.h>
 
                            int f[105][105];
                            void package(int *w,int *v,int n,int c)
                            {
                                for(int i=1;i&lt;=n;i++)//背包容量
                                    f[i][0] = 0;
                                for(int i=1;i&lt;=c;i++)//物品个数
                                    f[0][i] = 0;	
                                int i,j;	
                                for(i=1;i&lt;=n;i++)
                                {
                                    for(j=1;j&lt;=c;j++)
                                    {
                                        //当容量(注1)够放入第i个物品,并且放入之后的价值(放入之后他的价值+剩余背包容量对应的价值)要比不放(不放入他,背包当前容量对应的价值)大
                                        if(j>=w[i]&&f[i-1][j-w[i]]+v[i]>f[i-1][j])
                                        {
                                            f[i][j]=f[i-1][j-w[i]]+v[i];			
                                        }else
                                            f[i][j]=f[i-1][j];
                                    }
                                }
                            }
                            //1.(此容量并非剩余容量(相同当前背包容量下,上一步较少物品时对应的剩余的背包容量)而是当前背包总容量(并非全局背包总容量)即j非c) 
                            int main()
                            {
                                int c,n,w[105],v[105];
                                scanf("%d %d",&c,&n);
                                //c:背包容量     n:物品数量 
                                w[0]=0;
                                for(int i=1;i&lt;n+1;i++)
                                    scanf("%d",&w[i]);
                                v[0]=0;
                                for(int i=1;i&lt;n+1;i++)
                                    scanf("%d",&v[i]);
                            
                                int i,j;
                                package(w,v,n,c);
                                for(i=0;i&lt;=n;i++)
                                {
                                    for(j=0;j&lt;=c;j++)
                                        printf("%d ",f[i][j]);
                                    printf("\n");
                                }
                            
                            }
                            
                                   
                      </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Python:</div>
                    <pre class="language-javascript">
                        <code>
                            bag_size = 4
                            weight = [1, 3, 4]
                            value = [15, 20, 30]

                            rows, cols = len(weight), bag_size + 1
                            dp = [[0]*cols for _ in range(rows)]

                            # 初始化dp数组.
                            for i in range(rows):
                                dp[i][0] = 0
                            first_item_weight, first_item_value = weight[0], value[0]
                            for j in range(1, cols):
                                if first_item_weight &lt;= j:
                                    dp[0][j] = first_item_value

                            # 更新dp数组: 先遍历物品, 再遍历背包.
                            for i in range(1, rows):
                                for j in range(1, cols):
                                    if weight[i] > j:  # 说明背包装不下当前物品.
                                        dp[i][j] = dp[i - 1][j]  # 所以不装当前物品.
                                    else:
                                        # 定义dp数组: dp[i][j] 前i个物品里，放进容量为j的背包，价值总和最大是多少。
                                        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
                            print(dp)
                        </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Java:</div>
                    <pre class="language-javascript">
                      <code>
                        public class BagProblem {
                            public static void main(String[] args) {
                                int[] weight = {1,3,4};
                                int[] value = {15,20,30};
                                int bagSize = 4;
                                testWeightBagProblem(weight,value,bagSize);
                            }
                        
                            /**
                             * 动态规划获得结果
                             * @param weight  物品的重量
                             * @param value   物品的价值
                             * @param bagSize 背包的容量
                             */
                            public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
                        
                                // 创建dp数组
                                int goods = weight.length;  // 获取物品的数量
                                int[][] dp = new int[goods][bagSize + 1];
                        
                                // 初始化dp数组
                                // 创建数组后，其中默认的值就是0
                                for (int j = weight[0]; j &lt;= bagSize; j++) {
                                    dp[0][j] = value[0];
                                }
                        
                                // 填充dp数组
                                for (int i = 1; i &lt; weight.length; i++) {
                                    for (int j = 1; j &lt;= bagSize; j++) {
                                        if (j &lt; weight[i]) {
                                            /**
                                             * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
                                             * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                                             */
                                            dp[i][j] = dp[i-1][j];
                                        } else {
                                            /**
                                             * 当前背包的容量可以放下物品i
                                             * 那么此时分两种情况：
                                             *    1、不放物品i
                                             *    2、放物品i
                                             * 比较这两种情况下，哪种背包中物品的最大价值最大
                                             */
                                            dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                                        }
                                    }
                                }
                        
                                // 打印dp数组
                                for (int i = 0; i &lt; goods; i++) {
                                    for (int j = 0; j &lt;= bagSize; j++) {
                                        System.out.print(dp[i][j] + "\t");
                                    }
                                    System.out.println("\n");
                                }
                            }
                        }
                      </code>
                    </pre>
                </div>
            </el-collapse-item>
        </el-collapse>
    </div>
</template>

<script lang="ts" setup>
import { ref } from 'vue'
const activeNames = ref(['thinking'])
const handleChange = (val: string[]) => {
    console.log(val)
}
// 代码实现部分
import "vue-code-highlight/themes/prism-solarizedlight.css";
import "vue-code-highlight/themes/window.css";

</script>
